package javax;

public class Xp_0112 {
    //堆排
    //完全二叉树
    //落地  数组结构->脑补 父i-1/2  左2*i +1  右2*i+2  大根堆：所有的子根的最大数都是头节点  小根堆相反
    // 5 7 0 6 8  8 7 0 5 6

    public static int[] headsort(int[] arr){
        if (arr == null || arr.length<2){
            return arr;
        }
        //完成 大根堆
        for (int i = 0 ; i<arr.length;i++){
            heapInsert(arr,i);
        }
        //堆大小
        int heapsize =arr.length;
        XpUtils.swap(arr,0,--heapsize);
        while (heapsize>0){
            heapify(arr,0,heapsize);
            XpUtils.swap(arr,0,--heapsize);
        }
        return arr;
    }

    /**
     * @description: 完成大根堆  交换 O(n)
     * @throws
     * @author xupeng20
     * @date 2019/1/10 17:09
     */
    public static void heapInsert(int [] arr,int index){
        //当前数  比父节点大  换
        while (arr[index] > arr[(index -1)/2]){
            XpUtils.swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
    /**
     * @description: 排序 孩子先取出最大值  与父比较
     * @throws
     * @author xupeng20
     * @date 2019/1/10 17:09
     */
    public static void heapify(int[] arr,int index ,int heapsize){
        int left = index * 2+1;
        while (left<heapsize){
            //父子谁大
            int largest = (left+ 1)<heapsize && arr[left+1]>arr[left] ? (left + 1) : left;
            largest = arr[largest] > arr[index] ? largest: index;
            if (largest ==index){
                break;
            }
            //一定不是本身 和孩子换
            XpUtils.swap(arr,largest,index);
            index = largest;
            left = index * 2 +1;
        }
    }
    public static void main(String[] args){
        int[] arr = {5,7,0,6,8};
        headsort(arr);

        XpUtils.print(arr);
    }
    /**
     * 应用： 大根堆、加入数返回加入数中的最大数、预留100数组 []100 ->加入数之后 依次放入[] 每放入一次就进行一次堆调整  堆结构单独用  返回最大值 也就是0位置的最大值  + 并删除最大值（将最后一个数与第一个数进行兑换、在堆调整、删除最后一个（最大值））
     * 完全二叉树调整很快  因为我们只需要看一条路径、所以复杂度是高度   所以O(logn)
     * 调整堆排的时间复杂度：log1 + log2...+logn(高度)  创建大根堆要O(n) 空间没用O(1)
     * 少用 ：因为不稳定和常数项特别大
     */
}
